week2手寫作業 戴偉璿

第一題：

note:lim⁡x→∞k=k,lim⁡x→∞1x=0note:\displaystyle\lim_{x\to \infty}k=k,\displaystyle\lim_{x\to \infty}\cfrac{1}{x}=0

a.\text{a}. lim⁡n→∞3n+1n−1=lim⁡n→∞(3+1n)lim⁡n→∞(1−1n)=31=3\displaystyle\lim_{n\to \infty}\cfrac{3n+1}{n-1}=\cfrac{{\displaystyle\lim_{n\to \infty}(3+\frac{1}{n}})}{{\displaystyle\lim_{n\to \infty}(1-\frac{1}{n}})}=\cfrac{3}{1}=3\\ b.\text{b}. lim⁡n→∞nn2+1=lim⁡n→∞1lim⁡n→∞(n+1n)=1n\displaystyle\lim_{n\to \infty}\cfrac{n}{n^2+1}=\cfrac{{\displaystyle\lim_{n\to \infty}1}}{{\displaystyle\lim_{n\to \infty}(n+\frac{1}{n}})}=\cfrac{1}{n}

note:f(n)∈O(g(n))⇔note:f(n)\in O(g(n))\Leftrightarrow ∃k>0,∃N,∀n>N,f(n)≤k⋅g(n)\exist k>0,\exist N,\forall n>N,f(n)\le k\cdot g(n)

c.\text{c}. f(n)∈O(2n)⟺f(n)∈O(2n+1)f(n)\in O(2^n)\Longleftrightarrow f(n)\in O(2^{n+1})\\ (1).proof  f(n)∈O(2n)⟹f(n)∈O(2n+1)(1).proof\;f(n)\in O(2^n)\Longrightarrow f(n)\in O(2^{n+1})\\ ∵f(n)∈O(2n)\because f(n)\in O(2^n)\\ ∴∃k≥0\therefore\exist k\ge 0,lim⁡n→∞f(n)2n=k\displaystyle\lim_{n\to \infty}\cfrac{f(n)}{2^n}=k\\

∴lim⁡n→∞f(n)2n+1=lim⁡n→∞f(n)2n⋅12=k⋅12\therefore\displaystyle\lim_{n\to \infty}\cfrac{f(n)}{2^{n+1}}=\displaystyle\lim_{n\to \infty}\cfrac{f(n)}{2^n}\cdot\cfrac{1}{2}=k\cdot\cfrac{1}{2}，仍為一常數

∴f(n)∈O(2n+1)\therefore f(n)\in O(2^{n+1})，成立

(2).proof  f(n)∈O(2n)⟸f(n)∈O(2n+1)(2).proof\;f(n)\in O(2^n)\Longleftarrow f(n)\in O(2^{n+1})\\ ∵f(n)∈O(2n+1)\because f(n)\in O(2^{n+1})\\ ∴∃k≥0\therefore\exist k\ge 0,lim⁡n→∞f(n)2n+1=l\displaystyle\lim_{n\to \infty}\cfrac{f(n)}{2^{n+1}}=l\\ ∴lim⁡n→∞f(n)2n=lim⁡n→∞f(n)2n+1⋅2=l⋅2\therefore\displaystyle\lim_{n\to \infty}\cfrac{f(n)}{2^n}=\displaystyle\lim_{n\to \infty}\cfrac{f(n)}{2^{n+1}}\cdot 2=l\cdot 2，仍為一常數

∴f(n)∈O(2n)\therefore f(n)\in O(2^n)，成立

由(1),(2),(1),(2),得證f(n)∈O(2n)⟺f(n)∈O(2n+1)f(n)\in O(2^n)\Longleftrightarrow f(n)\in O(2^{n+1})\\

d.\text{d}. f(n)∈O(n!)⟺f(n)∈O((n+1)!)f(n)\in O(n!)\Longleftrightarrow f(n)\in O((n+1)!)\\ (1).proof  f(n)∈O(n!)⟹f(n)∈O((n+1)!)(1).proof\;f(n)\in O(n!)\Longrightarrow f(n)\in O((n+1)!)\\ ∵f(n)∈O(n!)\because f(n)\in O(n!)\\ ∴∃k≥0\therefore\exist k\ge 0,lim⁡n→∞f(n)n!=k\displaystyle\lim_{n\to \infty}\cfrac{f(n)}{n!}=k

∴lim⁡n→∞f(n)(n+1)!=lim⁡n→∞f(n)n!⋅1n+1=lim⁡n→∞k⋅1n+1=0\therefore\displaystyle\lim_{n\to \infty}\cfrac{f(n)}{(n+1)!}=\displaystyle\lim_{n\to \infty}\cfrac{f(n)}{n!}\cdot\cfrac{1}{n+1}=\displaystyle\lim_{n\to \infty}k\cdot\cfrac{1}{n+1}=0，仍為一常數

∴f(n)∈O(n!)\therefore f(n)\in O(n!)\\

(2).proof  f(n)∈O(n!)⟸f(n)∈O((n+1)!)(2).proof\;f(n)\in O(n!)\Longleftarrow f(n)\in O((n+1)!)\\ ∵f(n)∈O((n+1)!)\because f(n)\in O((n+1)!)\\ ∴∃k≥0\therefore\exist k\ge 0,lim⁡n→∞f(n)(n+1)!=l\displaystyle\lim_{n\to \infty}\cfrac{f(n)}{(n+1)!}=l\\ ∴lim⁡n→∞f(n)n!=lim⁡n→∞f(n)(n+1)!⋅(n+1)=lim⁡n→∞l⋅(n+1)=∞\therefore\displaystyle\lim_{n\to \infty}\cfrac{f(n)}{n!}=\displaystyle\lim_{n\to \infty}\cfrac{f(n)}{(n+1)!}\cdot (n+1)=\displaystyle\lim_{n\to \infty}l\cdot (n+1)=\infty，無法收斂成一常數

假設命題成立，設f(n)=(n+1)!f(n)=(n+1)!，則

lim⁡n→∞f(n)n!=lim⁡n→∞(n+1)!n!=lim⁡n→∞n+1=∞\displaystyle\lim_{n\to \infty}\cfrac{f(n)}{n!}=\displaystyle\lim_{n\to \infty}\cfrac{(n+1)!}{n!}=\displaystyle\lim_{n\to \infty}n+1=\infty

此處產生矛盾，故f(n)∈O(n!)⟸f(n)∈O((n+1)!)f(n)\in O(n!)\Longleftarrow f(n)\in O((n+1)!)不成立，故原命題不成立。

∴f(n)∈O(n!)\therefore f(n)\in O(n!)

由(1),(2),(1),(2),得證f(n)∈O(n!)⟺f(n)∈O((n+1)!)f(n)\in O(n!)\Longleftrightarrow f(n)\in O((n+1)!)\\

上次沒證明出來的第四題

題目：序列開始時只包含一個正整數 nn，接著每次對此序列進行如下操作：在序 列中找到任意一個大於 1 的正整數 kk，接著把此數換成任意兩個正整數 a,ba, b，其中a+b=ka + b = k，則此操作得 a×ba × b 分，且數列會多出一項。重複進行以上操作，直到序列中的數均為 1 為止。試證：所有操作的得分總和為n2−n2\cfrac{n^2-n}{2}

假設命題成立，

n+1=(i)+(n−i+1)n+1=(i)+(n-i+1)，此步驟得i(n−i+1)=ni−i2+ii(n-i+1)=ni-i^2+i分

ii得分為：i2−i2\cfrac{i^2-i}{2}，n−i+1n-i+1得分為(n−i+1)2−(n−i+1)2\cfrac{(n-i+1)^2-(n-i+1)}{2}

將三步驟的分數相加：ni−i2+i+i2−i2+(n−i+1)2−(n−i+1)2=n2+n2ni-i^2+i+\cfrac{i^2-i}{2}+\cfrac{(n-i+1)^2-(n-i+1)}{2}=\cfrac{n^2+n}{2}，成立

故命題成立。